// https://leetcode.cn/problems/sum-of-subarray-minimums/
// Created by ade on 2022/9/6.
// 给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
//
//由于答案可能很大，因此 返回答案模 10^9 + 7 。
// 输入：arr = [3,1,2,4]
//输出：17
//解释：
//子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
//最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
//思路： 4, 2 2, 1 1 1, 1 1 1 3
// [11,81,94,43,3]
// 11, 11 11, 11 11 11, 11 11 11 11, 11 11 11 11 3
// [88,81,94,43,3]
// 88, 88 81, 88 81 81, 43 81 81 88, 3
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <stack>


using namespace std;

class Solution {
public:
    // 时间复杂度O(n2)会超时
//    int sumSubarrayMins1(vector<int> &arr) {
//        int len = arr.size();
//        long sum = 0;
//        unordered_map<int, int> m = {};
//        int minN = arr[len - 1];
//        for (int i = len - 1; i >= 0; i--) {
//            m[i] = min(minN, arr[i]);
//            minN = m[i];
//        }
//        // 输入：arr = [3,1,2,4,0,3,4]
//        // 子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
//        // 最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
//        // 思路： 4, 2 2, 1 1 1, 1 1 1 3
//        for (int i = len - 1; i >= 0; i--) {
//            vector<int> st = {};
//            st.assign(arr.begin() + i, arr.end());
//            while (!st.empty()) {
//                sum += *min_element(st.begin(), st.end());
//                st.pop_back();
//            }
//        }
//        long m = 1e9 + 7;
//        return sum % m;
//    }


    // 参考地址：https://leetcode.cn/problems/sum-of-subarray-minimums/solution/xiao-bai-lang-dong-hua-xiang-jie-bao-zhe-489q/
    int sumSubarrayMins(vector<int> &arr) {
        long long M = 1e9 + 7;
        int len = arr.size();
        vector<int> left(len, -1);
        vector<int> right(len, len);

        // {11, 81, 94, 43, 3};
        stack<int> st = {};
        // 找到左侧第一个  《《小于》》  自己的值 对应的位置
        for (int i = 0; i < len; i++) {
            while (st.size() && arr[i] < arr[st.top()]) st.pop();
            if (!st.empty()) left[i] = st.top();
            st.push(i);
        }

        st = {};
        // 找到右侧第一个  《《小于等于》》  自己的值 对应的位置
        for (int i = len - 1; i >= 0; i--) {
            while (st.size() && arr[i] <= arr[st.top()]) st.pop();
            if (!st.empty()) right[i] = st.top();
            st.push(i);
        }
        // 每个数的影响值相加
        long long sum = 0;
        for (int i = 0; i < len; i++) {
            sum += (long long) (arr[i]) * (i - left[i]) * (right[i] - i);
            if (sum >= M) sum -= M;
        }
        return (int) sum;
    }
};

int main() {
    Solution so;
    vector<int> nums = {11, 81, 94, 43, 3};
    cout << so.sumSubarrayMins(nums);
    return 0;
}